/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***给定一个数组，创建一个赫夫曼树                ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <list>
//c++中 std::sort 需要能够有可供速记访问的迭代器
//而list容器实现方法是链表，因为不具有该属性，也就不能使用std::sort排序
//list容器排序使用list::sort();
using std::cout;
using std::endl;
using std::list;
using std::string;
using std::vector;

class Node;
std::ostream &operator<<(std::ostream &out, const Node &node);
Node* createHuffmanTree(vector<int> &vec);

class Node
{
public:
    Node() = delete;
    string transToString()
    {
        return std::to_string(this->value);
    }
    Node(int value) : value(value), left(nullptr), right(nullptr) {}
    //供算法调用的函数，一定要重载<运算符，系统默认使用<
    Node(int value, Node* left, Node* right): value(value),left(left),right(right){}
    bool operator<(Node &node)
    {
        return value < node.value;
    }
    //排序使用的 谓词
    static bool lessThan(Node *node1, Node *node2)
    {
        return node1->value < (node2->value);
    }
    int getValue()
    {
        return value;
    }
    //二叉树的前序遍历
    static void preOrder(Node* node)
    {
        cout<<node->transToString()<<"\t";
        if (node->left!=nullptr){
            preOrder(node->left);
        }
        if (node->right!=nullptr){
            preOrder(node->right);
        }
    }
    ~Node()
    {
        Node* tempNode=this;
        if (tempNode->left!=nullptr){
            delete tempNode->left;
        }
        if (tempNode->right!=nullptr){
            delete tempNode->right;
        }
        if (tempNode!=nullptr){
            delete tempNode;
            tempNode=nullptr;
        }
    }
private:
    int value;
    Node *left;
    Node *right;
};
//用于比较list中元素大小的谓词

//传入数组，创建可以赫夫曼树
Node* createHuffmanTree(vector<int> &vec)
{
    //生成一个承载所有 node的 list容器
    list<Node *> listNode;
    for (auto item : vec)
    {
        listNode.push_back(new Node(item));
    }
    while (listNode.size() > 1)
    { //对容器的元素进行排序
        listNode.sort(Node::lessThan);
        //从列表中取出最小的两个节点，并且创建两个子节点的父节点
        auto leftNode = listNode.front();
        listNode.pop_front();
        auto rightNode = listNode.front();
        listNode.pop_front();
        Node *parent(new Node(leftNode->getValue() + rightNode->getValue(),leftNode,rightNode));
        //父节点，重新加入队列
        listNode.push_front(parent);
    }
    auto node=listNode.front();
    return node;
}

int main()
{
    vector<int> origiVec({13, 7, 8, 3, 29, 6, 1});
    auto node=createHuffmanTree(origiVec);
    Node::preOrder(node);
    if (node!=nullptr){
        delete node;
        node=nullptr;
    }
    return 0;
}